package swardToOffer.struct_4_tree;

/**
 * @Author ChanZany
 * @Date 2021/5/21 17:04
 * @Version 1.0
 * 面试题26：树的子结构
 * 题目：输入两棵二叉树A和B，判断B是不是A的子结构。
 * 思路：
 * 1.将B树的根节点与A树中各节点进行比较，比较成功则进入第二步骤
 * 2.比较成功所在节点可以将A树拆分为更小的两颗树CD，然后将B的左子树与树C进行比较，B的右子树与C进行比较
 * 3.B.left与C的比较，B.right与D的比较与第1步相同。
 * 从而是一个递归的解法
 * return bt.val==at.val && dfs(bt.left,at.left) && dfs(bt.right,at.right)
 */


public class SubstructureInTree {

    boolean hasSubtree(TreeNode rootA, TreeNode rootB) {
        if (rootA == null || rootB == null) return false;
        if (rootA.val == rootB.val) return helper(rootA, rootB);
        //1.找到相同的点
        return hasSubtree(rootA.left, rootB) || hasSubtree(rootA.right, rootB);
    }

    private boolean helper(TreeNode rootA, TreeNode rootB) {
        //2.判断该点下的两数是否相等，使用前序遍历
        if (rootB == null) return true;
        if (rootA == null) return false;
        if (rootA.val != rootB.val) return false;
        return helper(rootA.left, rootB.left) && helper(rootA.right, rootB.right);
    }

    public static void main(String[] args) {
        SubstructureInTree Main = new SubstructureInTree();
        TreeNode treeA = TreeUtil.build(new int[]{1, 2, 3, 4, 5}, 0, 4);
        TreeUtil.preOrder(treeA);
        TreeNode treeB = TreeUtil.build(new int[]{1, 3, 4}, 0, 2);
        System.out.println("..................");
        TreeUtil.preOrder(treeB);
        System.out.println(Main.hasSubtree(treeA, treeB));
    }

}
